package leetcode_900;

import java.util.ArrayList;
import java.util.List;

/**
 *@author 周杨
 *SplitArrayIntoFibonacciSequence_842 问一个整数String 能否被分割成若干Int 而且是斐波拉契数列
 *describe:用回溯 AC 55%
 *2018年11月1日 下午4:35:41
 */
public class SplitArrayIntoFibonacciSequence_842 {
	public List<Integer> splitIntoFibonacci(String S) {
        List<Integer> ls = dfs(new ArrayList<>(), S);//把空的给其搜
        return ls == null ? new ArrayList<>() : ls;
    }
    
    public List<Integer> dfs(List<Integer> last, String s) {
        if (s.length() == 0) return null;
        for (int i = 1; i <= s.length(); i++) {
            List<Integer> tmp = new ArrayList<>(last);//把原来的保存
            String st = s.substring(0, i);
            if (st.startsWith("0") && st.length() > 1) return null;//初始0 无效
            long val = Long.parseLong(st);
            if (val > Integer.MAX_VALUE) return null;//太大了
            int next = (int) val;//确定下一个数
            if (last.size() < 2) {//确定下一个数 
                tmp.add(next);
                List<Integer> ret = dfs(tmp, s.substring(i));//如果得到了合法的结果 那么就返回
                if (ret != null) return ret;
            } else {//判断是否合法
                int len = last.size();
                if (next == last.get(len - 1) + last.get(len - 2)) {
                    List<Integer> tp = new ArrayList<>(last);
                    tp.add(next);
                    if (i == s.length()) return tp;//遍历完了
                    List<Integer> ret = dfs(tp, s.substring(i));
                    if (ret != null) return ret;
                }
            }
        }
        return null;
    }
}
